1. Field of Invention
The present invention relates to a data retrieval apparatus for retrieving desired data from a number of data stored in a memory.
2. Description of Related Art
Conventionally, data retrieval apparatus are widely used. FIG. 12 is a block diagram showing an example of a conventional data retrieval apparatus that includes a control circuit 10 and a memory 20. The control circuit controls retrieval, register and deletion of data.
According to the data retrieval apparatus shown by FIG. 12, when a retrieval operation is carried out by a retrieval value KEY, the retrieval value KEY is provided as data and a retrieval start signal is transmitted. Further, when a register value INS is registered, the register value INS is provided as data and a register request signal is transmitted. Similarly, when a deletion value DEL is deleted, the deletion value DEL is provided as data and a deletion request signal is transmitted.
Although there are many methods for data retrieval, an explanation will be given for a data retrieval apparatus using a binary search method as follows.
Consider a series of data comprising a[0], a[1], a[2], . . . , a[nxe2x88x921]. According to the binary search method, it is assumed that the series of data is ordered in an ascending order or a descending order If the ascending order is assumed, then:
a[0] less than a[1] less than a[2] less than . . .  less than a[nxe2x88x921].
The binary search method searches for an element which is equal to the retrieval value KEY from the series of data. A range of retrieval is initially from a[0] to a[nxe2x88x921] (the entire series of data). In general, the binary search method is a process of dividing the series of data in 2, selecting one portion of the series of data in which the retrieval value KEY is considered to exist, further dividing the selected portion of the series of data in 2 end so on. This process is repeated and a number of elements in the retrieval range is halved at each selection. The retrieval operation is finished when a number of elements in the retrieval range becomes 1, or the retrieval value KEY coincides with a certain element of the series of data.
FIG. 13 shows a flow chart of the binary search method; FIG. 14 shows address transitions of a central element in the retrieval range; and FIG. 15 shows a timing diagram of the retrieval operation. An explanation will be given by specifically pointing out the retrieval operation of the data retrieval apparatus in reference to FIG. 13 through FIG. 15 as follows.
For example, if the series of data includes 15 elements, addresses of memory locations storing the series of data may be 0 through 14. Assume that the retrieval value is designated by notation KEY and data stored in the memory addresses 0 through 14 are respectively designated by notations MEM[0] through MEM[14]. An explanation will be given of an example of a case in which the data have the following relationships:
MEM[0] less than MEM[1] less than MEM[2] less than  . . .  less than MEM[14];
and
MEM[5] less than MEM[6] less than MEM[7],
where the retrieval value KEY coincides with data of memory address 6.
At step 1301 of FIG. 13, S=0, E=14. Here, notations S, E and M mentioned below are variables in executing the flow in which notation S designates a first address number in a retrieval range, notation E designates a final address number in the retrieval range and notation M designates an address number at a center of the retrieval range.
Next, at step 1302, the central element in the range of MEM[0] to MEM[14] is generated as M=(S+B)/2=7. Accordingly, the center element becomes MEM[7]. Then, the central element MEM[7] is read from the memory 20 (cycle 1 of FIG. 15).
At step 1303, if a number of elements in the retrieval range is Exe2x88x92S+1=15 which does not equal to 1, the processing is shifted to step 1304. At step 1304, the retrieval value KEY is compared with the central element MEM[7] (cycle 2 of FIG. 15) to determine whether the retrieval value KEY is greater than, equal to or less than the central element MEM[7].
If the retrieval value KEY is less than MEM[7] (KEY less than MEM[7]), then the retrieval value KEY (MEM[6]) is in a range less than the central element MEM[7] and the processing is shifted to step 1305. At step 1305, the value of E is set equal to the value of M which is 7. Thus, the retrieval range becomes a range of MEM[0] through MEM[7]. Then the processing returns to step 1302.
At step 1302, a next central element of the successive retrieval range is generated. The central element at this time becomes MEM[3] which is obtained by omitting numbers less than a decimal point from M=(S+E)/2=3.5 and MEM[3] is read from the memory 20 (cycle 3 of FIG. 15). At step 1303, the number of elements in the retrieval range is 8 which does not equal to 1 and accordingly, the operation proceeds to step 1304. At step 1304, the retrieval value is compared with the central element (cycle 4 of FIG. 15) and the operation proceeds to step 1306 since KEY greater than MEM[3]. In the processing at step 1306, by setting S=M+1=4, the retrieval range is narrowed a range of MEM[4]through MEM[7].
Returning again to the step 1302, the central element MEM[5] is generated. At step 1303, the number of elements of the retrieval range is 4 which is not equal to 1, and accordingly, the operation proceeds to step 1304. According to the comparison at this step, KEY greater than MEM[5], thus the operation proceeds to step 1306 and S=M+1=6 (cycles 5, 6 of FIG. 15).
Returning again to step 1302, the central element is generated and MEM[6] is provided. At step 1303, the number of elements of the retrieval range is 2, thus the operation proceeds to step 1304 and KEY=MEM[6] is found by the comparison. Accordingly, the retrieval operation is finished (cycles 7, 8 of FIG. 15) and MEM[6] constitutes the retrieval result.
Next, an explanation will be given of operation of registering data.
FIG. 16 shows an outline of operation in registering a register value INS into a series of effective data of a[0] through a[11]. For this example, INS is larger than a[5] and smaller than a[6], that is, a [5] less than INS less than a[6].
The series of data must always be stored in memory in an ascending (or descending) order such that retrieval of data can be carried out. Therefore, in registering data, a position in memory where data is to be registered must be searched and a free memory location for the register data to be inserted must be obtained by shifting data already in the memory one by one and thereafter, the register data to be inserted must be written into the free memory location. Data registering operation is provided with the insertion operation described above when there is not an element which is equal to the register value in a series of data and is provided with an overwriting operation when there exists an element which is equal to the register value.
FIG. 17 shows a flow chart of the registering operation which includes both the insertion and overwriting operations. FIG. 18 shows operational timings of the registering operation. An explanation will be given by pointing out a specific example of registering operation of data in reference to FIG. 17 and FIG. 18.
Assume that there are 15 elements in the series of data. Thus, addresses of memory locations of the series of data may be designated by 0 through 14. Also assume that 12 elements of effective data are stored at addresses 0 through 11 is an order according to the size of each of the effective data. That is, when the number of the effective data is designated by notation m (i.e., m=12) and when the data is represented by MEM[0] through MEM[11], there is established a relationship of MEM[0] less than MEM[1] less than MEM[2] less than  . . .  less than MEM[11]. Thus, nothing is registered at address 12 and thereafter. Consider here a case in which a register value is designated by notation INS and MEM[5] less than INS less than MEM[6].
At step 1701 of FIG. 17, retrieval operation is carried out with the register value INS as a retrieval value (cycle 1 through cycle 8 of FIG. 18). Overwriting operation is carried out when there is an element in coincidence with the register value INS. When an address storing a coincident element is designated by M, then INS is written to MEM[M] (steps 1702, 1709). However, assume as an example that there is no element in coincidence with the register value INS. Then an insertion operation is carried out and an insertion address is M=6 (step 1702).
At step 1703, S=mxe2x88x921=11, D=m=12, and E=M=6. In this case, notation m designates a number of registered data and notation M designates an address of the inserting data as mentioned above. Notations S, D and E represent variables in executing the flow as mentioned above.
In steps 1704-1707, movement of data is carried out. At step 1704, a determination is made of whether the movement of data is finished. For the above example, E less than D, accordingly, data at address 11 is read (step 1705; cycle 9 of FIG. 18) and is written to address 12 (step 1706, cycle 10). At step 1707, S and D are updated and S=10 and D=11. Operation of step 1704 to step 1707 is repeated until E=D (cycles 11 through 20).
At step 1704, when E=D=6, the original data MEM[6] through MEM[11] have been moved from addresses 6 through 11 to addresses 7 through 12. Finally, at step 1708, the effective element number m is incremented by 1 (step 1708) and the register value INS is written to address M where M=6 (step 1709, cycle 21).
Next, an explanation will be given of deletion of data.
FIG. 19 shows an outline of an operation when a portion of deletion data DEL is deleted from the 12 elements of the series of effective data of a[0] through a[11]. Also in deleting data, data must be stored in memory in an ascending (or descending) order such that retrieval operation can be carried out. Accordingly, a position of data to be deleted must be searched and a space of deleted data must be filled by shifting data in the memory one by one.
FIG. 20 shows a flow chart of the data deleting operation and FIG. 21 shows a timing diagram of the deleting operation. An explanation will be given by way of a specific example in reference to FIG. 20 and FIG. 21.
Assume that a number of data of a series of data is 15. Thus, addresses of the series of data in memory may be 0 through 14 and assume that 12 effective data are stored in addresses 0 through 11 in the memory. If m is a total number of effective data, then m=12. If the effective data is represented by MEM[0] through MEM[11], then MEM[0] less than MEM[1] less than MEM[2] less than  . . .  less than MEM[11] and nothing is registered at address 12 and thereafter. In this case, a deletion value is designated by notation DEL. For the following discussion, assume that MEM[5] less than DEL=MEM[6] less than MEM[7].
First, at step 2001, a retrieval operation is carried out with the deletion value DEL as a retrieval value (cycle 1 through cycle 8 of FIG. 21). If there is no element in coincidence with the deletion value DEL, the deleting operation cannot be carried out and therefore, the processing is finished.
Assume that there exists an element in coincidence with the deletion value DEL. At step 2002, if an address storing a coincident element is designated by notation M, then MEM[M] constitutes a deletion object. At this point in the example, M is 6 as mentioned above.
At step 2003, S, D and E are set as: S=M+1=7, D=M=6, E=m=12, and the operation proceeds to step 2004 to determine if a movement of data is completed. If the movement of data is not completed, the operation proceeds through steps 2004, 2005, 2006 and 2007 until the movement of data is completed.
At this point in the example, E greater than D. Accordingly, address 7 is read (step 2005, cycle 9) and is written to address 6 (step 2006, cycle 10). At step 2007, S and D are updated as S=S and D=7. The operation proceeds from step 2004 to step 2007 until E=D (cycles 11 through 18).
At step 2004, when E=D=12, the original data MEM[7] through MEM[11] at addresses 7 through 11 are moved to addresses 6 through 10. At step 2008, the effective element number m is decremented by 1.
By the above-described operation, data retrieval as well as register and deletion of data are carried out based on the binary search method. According to the retrieval operation by the binary search method, as shown by, for example, FIG. 15, reading of data from a memory and comparison between the read data and the retrieval value KEY are carried out alternately and memories are not used during substantially a half time period of the retrieval operation which is wasteful.
In view of the above-described situation, it is an object of the invention to provide a data retrieval apparatus adopting binary search method and capable of carrying out high-speed retrieval operation.
In order to achieve the above-described object, according to an aspect of the invention, there is provided a data retrieval apparatus comprising:
3 or 4 memories;
an address converting circuit in which in a case where a logical address space is divided into 2 banks of a bank constituting a set of even number addresses and a bank constituting a set of odd number addresses and either or both of banks of the two banks are expressed by binary numbers and are divided into a bank constituting a set of addresses where an even number of bits of xe2x80x9c1xe2x80x9d are present and a bank constituting a set of addresses where an odd number of bits of xe2x80x9c1xe2x80x9d are present, a total of 3 or 4 banks of the logical address space are mapped in physical address spaces of respectives of the 3 or 4 of memories; and
a control circuit which is a control circuit for carrying out a retrieval of data stored to the memories by a binary search method by using a given key data and which carries out the retrieval including a cycle simultaneously executing a comparison of the key data with the data read from the memories and an operation of reading from the memories two pieces of the data which are scheduled to carry out the comparison successively.
Further, according to a data retrieval apparatus of other aspect of the invention achieving the above-described object, the memories store the data by aligning the data in an ascending order or a descending order, the retrieval apparatus retrieves an insertion position or a deletion position, further, moves data at an address at an order higher than that of the insertion position to a higher order side by 1 address in inserting data and moves data at an order higher than an order of an address where data to be deleted is disposed to a lower order side by 1 address in deleting data in order to maintain an aligned state.
Further, according to a data retrieval apparatus of other aspect of the invention achieving the above-described object, the memories are constituted by a region for storing register data constituting an object of the retrieval and a region storing associative data accompanied to a result of the retrieval of the register data.
Further, according to other aspect of the invention achieving the above-described object, there is provided a data packet distributing system comprising:
an address data obtaining circuit for sampling address data from a data packet;
a data retrieval apparatus for carrying out a comparison between the sampled address data and register data stored in memories and an operation of reading the register data constituting an object of a successive comparison in a same cycle; and
a distributed destination data forming circuit for forming distributed destination data in reference to a retrieval finish signal, a coincidence signal and coincidence data constituting a result of retrieval of the data retrieval apparatus.
Further, according to other aspects of the invention, there is a method for searching for a retrieval key in a plurality of data elements that are stored in an order based on magnitudes of the data elements, comprising:
(a) retrieving a center data element from the data elements;
(b) concurrently comparing the center data element with the retrieval key to generate a compare result, and retrieving a greater data element and a lesser data element from the data elements;
(c) selecting either the greater or the lesser data elements as the center data element based on the compare result; and
(d) repeating steps (b) and (c) until a desired difference between addresses of the greater and the lesser data elements is reached; and
(e) outputting a retrieval address of a last center data element.
The above method further comprising:
storing data elements having even logical addresses in a first memory;
storing data elements having odd logical addresses that have binary values with an even number of xe2x80x9c1xe2x80x9ds in a second memory; and
storing data elements having odd logical addresses that have binary values with an odd number of xe2x80x9c1xe2x80x9ds in a third memory, the first, second and third memories being independently readable.
In addition, the method further comprising:
storing data elements having even logical addresses that have a binary value with an even number of xe2x80x9c1xe2x80x9ds in the first memory; and
storing data elements having even logical addresses that have a binary value with and odd number of xe2x80x9c1xe2x80x9ds in a fourth memory.